package com.gjx.leetcode;

import java.util.ArrayList;
import java.util.List;

//118. 杨辉三角
//给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
//
//
//
//在杨辉三角中，每个数是它左上方和右上方的数的和。
//
//示例:
//
//输入: 5
//输出:
//[
//     [1],
//    [1,1],
//   [1,2,1],
//  [1,3,3,1],
// [1,4,6,4,1]
//]

public class Solution118 {
	public List<List<Integer>> generate(int numRows) {
		List<List<Integer>> res = new ArrayList<>();
		if (numRows <= 0) {
			return res;
		}
		
		List<Integer> first = new ArrayList<>();
		first.add(1);
		res.add(first);
		
		if (numRows == 1) {
			return res;
		}
		
		List<Integer> second = new ArrayList<>();
		second.add(1);
		second.add(1);
		res.add(second);
		
		if (numRows == 2) {
			return res;
		}
		
		for (int i=2; i<numRows; i++) {
			
			List<Integer> list = new ArrayList<>();
			list.add(1);
			
			List<Integer> up = res.get(i-1);
			
			for (int j=0; j<up.size()-1; j++) {
				list.add(up.get(j) + up.get(j+1));
			}
			
			list.add(1);
			
			res.add(list);
			
		}
		
		return res;
	}
}